package 强化训练;

import java.util.Scanner;

public class day32斐波那契凤尾 {
    public static void main(String[] args) {
        long[] fb = new long[100001];
        fb[1] = 1;
        fb[2] = 2;
        int flag = 0;
        for (int i = 3; i < 100001; i++) {
            fb[i] = fb[i-1] + fb[i-2];
            if (flag == 0 && fb[i] > 1000000){
                flag += i;
            }
            fb[i] = fb[i] % 1000000;
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            if (n < flag){//输入3，3的结果小于6位数，直接输出3的结果，前面不用补0
                System.out.printf("%d\n",fb[n]);
            }else {//否则，n的结果过大于6位数，前面补0，在输出
                System.out.printf("%06d\n",fb[n]);
            }
        }
    }
}
